package com.jorenwu.asymmetric;

import java.math.BigInteger;

public class ShanksFactorization implements Factorization
{
	private long p, q, g, u;
	private long Z[];
	
	public ShanksFactorization(long p,long g, long u)
	{
		this.g = g;
		this.p = p;
		this.q = p-1;
		this.u = u;
	}

	public long factorize()
	{
		return shanksFactorization();
	}

	private long shanksFactorization()
	{
		long m, v, k, Y,X,j;
		// man steps
		m = (long) Math.sqrt(q) + 1;
		Y = (long) Math.pow(g, m) % p;
		Z = new long[(int) m];
		for (k = 0; k < m; k++)
		{
			Z[(int) k] = (long) Math.pow(Y, k) % p;
		}
		// baby steps
		Y = (new BigInteger(String.valueOf(g))).modInverse(
				new BigInteger(String.valueOf(p))).longValue();
		X=u;
		j=0;
		k=findL(X);
		while(k==-1)
		{
			X=X*Y%p;
			++j;
			k=findL(X);
		}
		v=k*m+j;
		return v;
	}
	
	long findL(long k)
	{
		for(int i=0;i<Z.length;i++)
		{
			if(Z[i]==k) return i;
		}
		return -1;
	}
}
